package com.dai.code;

import com.dai.common.Node;

import java.util.HashSet;

/**
 * @author daijiyong
 */
public class LinkedCircle {
    public static void main(String[] args) {
        Node list = new Node(1);
        Node temp = list;
        Node cross = null;
        for (int i = 2; i < 10; i++) {
            temp.next = new Node(i);
            temp = temp.next;
            if (i == 5) {
                cross = temp;
            }
        }
        // 在节点5的位置制造一个环
        temp.next = cross;

        System.out.printf("链表[%s]是否存在环：%s\n", list.toStringWhenCircle(), isLinkedCircle(list));
        System.out.printf("链表[%s]是否存在环：%s\n", list.toStringWhenCircle(), isLinkedCircle2(list));
        System.out.printf("链表[%s]存在环的入口节点：%d\n", list.toStringWhenCircle(), findLinkedCircle(list).value);
        System.out.printf("链表[%s]存在环的入口节点：%d\n", list.toStringWhenCircle(), findLinkedCircle2(list).value);
    }


    public static Boolean isLinkedCircle(Node list) {

        if (list == null || list.next == null) {
            return false;
        }

        HashSet<Node> nodeHashSet = new HashSet<>();
        Node header = list;
        // 当第二次遍历到环入口的时候，则跳出循环
        while (nodeHashSet.add(header)) {
            header = header.next;
            if (header == null) {
                return false;
            }
        }
        return true;
    }

    public static Boolean isLinkedCircle2(Node list) {

        if (list == null || list.next == null) {
            return false;
        }

        Node faster = list.next.next;
        Node slower = list.next;
        while (faster != slower) {
            if (faster == null || faster.next == null) {
                return false;
            }
            // faster指针一次走两下
            faster = faster.next.next;
            // slower指针一次走一下
            slower = slower.next;
        }
        return true;
    }


    public static Node findLinkedCircle(Node list) {

        if (list == null || list.next == null) {
            return null;
        }

        HashSet<Node> nodeHashSet = new HashSet<>();

        // 当第二次遍历到环入口的时候，则跳出循环
        while (nodeHashSet.add(list)) {
            list = list.next;
            if (list == null) {
                return null;
            }
        }
        return list;
    }

    public static Node findLinkedCircle2(Node list) {

        if (list == null || list.next == null) {
            return null;
        }

        Node faster = list.next.next;
        Node slower = list.next;
        while (faster != slower) {
            if (faster == null || faster.next == null) {
                return null;
            }
            faster = faster.next.next;
            slower = slower.next;
        }
        // 让另一个指针从链表头开始遍历
        // 让faster或者slower从相交点同步遍历
        // 他们再次的相交点就是环的入口节点
        while (faster != list) {
            faster = faster.next;
            list = list.next;
        }

        return faster;
    }
}
